package com.cn.codebrush.二分查找;

import java.util.*;

/**
 * @Author Boolean
 * @Date 2022/5/11 22:54
 * @Version 1.0
 */
public class No349两个数组的交集 {
    public static void main(String[] args) {
        int[] nums1 = {1,2,2,1};
        int[] nums2 = {2,2};
        /*int[] nums1 = {1};
        int[] nums2 = {1};*/
        /*int[] nums1 = {1,2};
        int[] nums2 = {2,1};*/
        System.out.println(intersection(nums1,nums2));
    }

    public static int[] intersection(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        List<Integer> list = new ArrayList<Integer>();

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        for(int i=0;i<len1;i++){
            if(i>0 && nums1[i] == nums1[i-1]){continue;}
            int left = 0,right = len2;
            while(left<right){
                int mid = (left+right)/2;
                if(nums2[mid] == nums1[i]){
                    list.add(nums1[i]);
                    break;
                }else if(nums2[mid] > nums1[i]){
                    right = mid;
                }else {
                    left = mid+1;
                }
            }
        }

        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
